package cn.edu.ncepu;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CRTBigInteger {

    // 扩展欧几里得算法（BigInteger版）
    private static BigInteger[] extendEuclid(BigInteger a, BigInteger b) {
        if (a.compareTo(b) < 0) {
            BigInteger[] temp = extendEuclid(b, a);
            return new BigInteger[]{temp[1], temp[0]};
        }

        List<BigInteger> coefficients = new ArrayList<>();
        while (b.compareTo(BigInteger.ZERO) != 0) {
            coefficients.add(a.divide(b));
            BigInteger temp = b;
            b = a.mod(b);
            a = temp;
        }

        BigInteger x = BigInteger.ONE;
        BigInteger y = BigInteger.ZERO;
        Collections.reverse(coefficients);

        for (BigInteger i : coefficients) {
            BigInteger tempX = x;
            x = y;
            y = tempX.subtract(y.multiply(i));
        }

        return new BigInteger[]{x, y};
    }

    // 模逆元（BigInteger版）
    private static BigInteger modularInverse(BigInteger a, BigInteger m) {
        if (!a.gcd(m).equals(BigInteger.ONE)) {
            throw new IllegalArgumentException("a和m不互质，不存在模逆元！");
        }
        BigInteger[] result = extendEuclid(a, m);
        BigInteger x = result[0];

        while (x.compareTo(BigInteger.ZERO) < 0) {
            x = x.add(m);
        }

        return x;
    }

    // 中国剩余定理（BigInteger版）
    public static BigInteger crt(BigInteger[] aArray, BigInteger[] mArray) {
        if (aArray.length != mArray.length) {
            throw new IllegalArgumentException("余数数组和模数数组长度必须一致！");
        }

        // 计算模数乘积 mPi
        BigInteger mPi = BigInteger.ONE;
        for (BigInteger m : mArray) {
            mPi = mPi.multiply(m);
        }

        BigInteger x = BigInteger.ZERO;
        for (int i = 0; i < aArray.length; i++) {
            BigInteger a = aArray[i];
            BigInteger m = mArray[i];
            BigInteger b = mPi.divide(m);
            BigInteger inv = modularInverse(b, m);
            x = x.add(a.multiply(b).multiply(inv));
        }

        return x.mod(mPi);
    }

    public static void main(String[] args) {
        // 测试用例
        BigInteger[] aArray = {BigInteger.valueOf(2), BigInteger.valueOf(3), BigInteger.valueOf(2)};
        BigInteger[] mArray = {BigInteger.valueOf(3), BigInteger.valueOf(5), BigInteger.valueOf(7)};
        BigInteger result = crt(aArray, mArray);
        System.out.println("CRT求解结果（BigInteger）：" + result);

        // 验证
        for (int i = 0; i < aArray.length; i++) {
            BigInteger a = aArray[i];
            BigInteger m = mArray[i];
            System.out.printf("x mod %s = %s，预期：%s → %s%n",
                    m, result.mod(m), a, result.mod(m).equals(a) ? "正确" : "错误");
        }
    }
}